package treeStudy;

public class VerifySquenceOfBST {

    /**
     * 剑指offer JZ23 二叉搜索树的后序遍历序列
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜索树）
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] sequence = new int[]{
                4,6,7,5
        };
        VerifySquenceOfBST(sequence);
    }

    public static boolean VerifySquenceOfBST(int [] sequence) {
        return dfs(sequence, 0, sequence.length - 1);
    }
    public static boolean dfs(int[] sequence, int low, int heigh){
        if(low >= heigh){
            return true;
        }
        int index = low - 1;
        //得到第一个大于最后一个元素的值
        for(int i = low; i < heigh; i++){
            if (sequence[i] > sequence[heigh]){
                index = i;
                break;
            }
        }
        for(int j = index + 1; j < heigh; j++){
            if(sequence[j] < sequence[heigh]){
                return false;
            }
        }

        return dfs(sequence, low, index - 1) && dfs(sequence, index < low?low:index, heigh - 1);
    }
}
